package middle;

/**
 * 给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 *
 * 测试用例的答案是一个32-位 整数。
 *
 * 子数组 是数组的连续子序列。
 *
 * 链接：https://leetcode.cn/problems/maximum-product-subarray
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class MaximumProductSubarray {
    /**
     * 这道题跟LeetCode 53题类似，唯一不同的是，乘积可能会受到负数的影响。
     * 比如原本最大的值，乘以负数后得到是最小的值（最大的负数）。
     * 所以，我们需要记录一下最小的值，当遇到负数的时候，能保证其得到的是最大值。
     * */
    class Solution {
        public int maxProduct(int[] nums) {
            int iMax = nums[0];
            int iMin = nums[0];
            int max = nums[0];
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] < 0) {
                    int temp = iMax;
                    iMax = iMin;
                    iMin = temp;
                }
                iMax = Math.max(iMax * nums[i], nums[i]);
                iMin = Math.min(iMin * nums[i], nums[i]);
                max = Math.max(max, iMax);
            }
            return max;
        }
    }

    /**
     * 0ms的方法， 十分巧妙。
     * 其实当我们数组中的负数，是偶数的时候，最大的值肯定就是所有数相乘
     * 如果数组中的负数是奇数位的时候，那么这个时候就可以将数组分为两部分
     * 而这个分割线，就是从左到右 或者 从右到左乘积时的最后一个负数。
     * 比如 8 2 -2 4 -1 5 -5 3
     * 如果我们从左开始往右边数，最后一个负数就是倒数第二个-5
     * 在乘积的过程中，我们需要去记录最大值。
     *
     * 如果我们从右边开始往左边数，那么最后一个负数就是第三位的-2
     * 那么这个时候的最大值就是从4一直乘到最后一个数3。
     *
     * 8 2 -2 0 3 -3 4 -1 9
     * 注意： 如果在乘的过程中遇到0，那我们应该重新开始新的乘积。
     *
     * 这个表述如果不清楚的话，直接看代码，还是很好理解的。
     * */
    class Solution1 {
        public int maxProduct(int[] nums) {
            int max = nums[0];
            int d = 1;
            // 从左到右数
            for (int n : nums) {
                d *= n;
                max = Math.max(max, d);
                if (n == 0) {
                    d = 1;
                }
            }
            d = 1;
            // 从右到左数
            for (int i = nums.length - 1; i >= 0 ; i--) {
                d *= nums[i];
                max = Math.max(max, d);
                if (nums[i] == 0) {
                    d = 1;
                }
            }
            return max;
        }
    }
}
